/**
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 *
 * @format
 * @lc app=leetcode.cn id=34 lang=javascript
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
    let [left, right, mid] = [0, nums.length - 1, 0]
    // count：记录循环次数，超过数组长度一半时说明不存在 target
    let count = 0
    // 二分法寻找 target
    while (left < right && count < nums.length / 2 + 1) {
        if (nums[mid] == target) {
            left = right = mid
            break
        } else if (nums[mid] < target) {
            left = mid
            // +1 防止向下取整导致的漏查
            mid = Math.floor((left + right + 1) / 2)
        } else {
            right = mid
            mid = Math.floor((left + right) / 2)
        }
        count++
    }
    // 若不存在 target
    if (nums[mid] != target) return [-1, -1]
    // 调整左右指针，指向 target 的 start 和 end
    let [flagL, flagR] = [true, true]
    while (true) {
        flagL = nums[left - 1] == target
        flagR = nums[right + 1] == target
        if (flagL) left--
        if (flagR) right++
        if (!(flagL || flagR)) break
    }
    return [left, right]
}
// debugger
// const nums = [1, 2, 3]
// const target = 3
// const result = searchRange(nums, target)
// console.log(result)
// @lc code=end
